package 剑指offer.demo5;
//https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?
/*
动态规划
 */
public class 连续子数组的最大和 {
    public int FindGreatestSumOfSubArray(int[] array) {
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int max = array[0];
        //循环遍历数组array进行操作
        for (int i = 1; i < array.length; i++) {
            //使dp[i]一直保存当前序列前的最大值，如果前序列比当前元素都小，当然抛弃前序列重新开始，
            dp[i] = Math.max(dp[i - 1] + array[i] , array[i]);
            //最大值另外单独保存
            max = Math.max(dp[i] , max);
        }
        return max;
    }
}
